class Solution
{
public:
    vector<int> rearrangeBarcodes(vector<int> &barcodes)
    {
        unordered_map<int, int> codeCount;
        for (int code : barcodes)
        {
            ++codeCount[code];
        }

        auto compare = [&](int code1, int code2)
        {
            return codeCount[code1] < codeCount[code2];
        };

        priority_queue<int, vector<int>, decltype(compare)> q(compare);
        for (auto [code, _] : codeCount)
        {
            q.push(code);
        }

        vector<int> result;
        while (!q.empty())
        {
            int largest = q.top();
            q.pop();
            result.push_back(largest);
            if (q.empty())
            {
                break;
            }
            else
            {
                int secondLargest = q.top();
                q.pop();
                result.push_back(secondLargest);
                --codeCount[largest];
                --codeCount[secondLargest];
                if (codeCount[largest] != 0)
                {
                    q.push(largest);
                }
                if (codeCount[secondLargest] != 0)
                {
                    q.push(secondLargest);
                }
            }
        }
        return result;
    }
};